In white-box cryptography and more in general software obfuscation, computations are often performed on encoded values instead of plain values. Reverse engineering of the obfuscated software is harder if computations are performed on encoded values, instead of on the plain values themselves.
After the encoding, regular operations, like addition or multiplication, can no longer be performed using a computer's built-in primitives. The straightforward addition of encoded values does not normally result in the encoding of the addition of the values. The same holds for multiplication. In a formula: E(x)+E(y)≠E(x+y), for most x and y; E denotes the encoding function.
A solution to this problem is to introduce addition (A) and multiplication (M) tables. The tables take two encoded values as input and produce an encoded value as output that corresponds to the encoding of the addition or multiplication operation. The tables may be defined as: A(E(x),E(y))=E(x+y); M(E(x),E(y))=E(xy). These tables allow arithmetic to be performed directly on encoded values.
The obfuscated addition and multiplication using tables suffers from at least two drawbacks. First, the tables can become quite large. If x and y are represented as 1 bits, each table needs 22ll bits.
Second, such large tables may be easily found in software. Worse, the tables might still be identified as addition or multiplication operations even though they are encoded; for example, through properties of these functions that are preserved in the encoding. For example, the multiplication table satisfies M(E(0),E(x))=E(0). An attacker may use this and similar properties to guess which operation the tables represent.